import java.util.Iterator;
import java.util.List;

public class Main {
	public static void main(String[] args) {
		/* This first puzzle is easy to solve.
		   1 4 2
		   3   5
		   6 7 8 */
//		int[] puzzle = {1, 4, 2, 3, 0, 5, 6, 7, 8};

		/* This second puzzle is more difficult.
		   2 6 7
		     5 1
		   8 3 4 */
//		int[] puzzle = {2, 6, 7, 0, 5, 1, 8, 3, 4};

		/* This third puzzle (from the textbook) is even harder.
		   7 2 4
		   5   6
		   8 3 1 */
//		int[] puzzle = {7, 2, 4, 5, 0, 6, 8, 3, 1};

		/* This forth puzzle is the most difficult yet, but the solution sequence
		   follows a simple pattern.
		   8 7 6
		   5 4 3
		   2 1   */
//		int[] puzzle = {8, 7, 6, 5, 4, 3, 2, 1, 0};
		
		/* This fifth puzzle one of the two puzzles with the longest solution
		   sequence.
		   8 7 6
		     4 1
		   2 5 3 */
//		int[] puzzle = {8, 7, 6, 0, 4, 1, 2, 5, 3};

//		SlidingPuzzle start = new SlidingPuzzle(puzzle);
//		start.randomize();
//		SlidingPuzzle goal = new SlidingPuzzle(start.getSize());
		
//		State start = new TranspositionPuzzle("leaf");
//		State goal = new TranspositionPuzzle("flea");
		
		StateWithCost start = new TranspositionPuzzle("leaf");
		StateWithCost goal = new TranspositionPuzzle("flea"); 
		
//		BreadthFirstSearch.solve(start, goal);
//		DepthFirstSearch.solve(start, goal);

		List<StateWithCost> result = UniformCostSearch.solve(start, goal);
		if (result != null){
			Iterator<StateWithCost> itr = result.iterator();
			while (itr.hasNext())
				System.out.println(itr.next());
			System.out.println("Solution in " + (result.size()-1) + " moves");
		}
		
		else
			System.out.println("No solution");
	
/*		
		List<State> result = IDDepthFirstSearch.solve(start, goal);
		if(result != null) {
			for(State state:result)	{
				System.out.println(state);
			}
			System.out.println("Solution in " + (result.size() -1) + " moves");
		}
*/
	}
}